By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 27, Issue 4, pp. 917-1220

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Fast Gossiping by Short Messages

Jean-Claude Bermond, Luisa Gargano, Adele A. Rescigno, and Ugo Vaccaro

pp. 917-941

BibTeX  Abstract Full Text:  PDF

Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference

Reuven Bar-Yehuda, Dan Geiger, Joseph (Seffi) Naor, and Ron M. Roth

pp. 942-959

BibTeX  Abstract Full Text:  PDF

Planar Integer Linear Programming is NC Equivalent to Euclidean GCD

D. F. Shallcross, V. Y. Pan, and Y. Lin-Kriz

pp. 960-971

BibTeX  Abstract Full Text:  PDF

All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings

Jeanette P. Schmidt

pp. 972-992

BibTeX  Abstract Full Text:  PDF

Bounding the Power of Preemption in Randomized Scheduling

Ran Canetti and Sandy Irani

pp. 993-1015

BibTeX  Abstract Full Text:  PDF

Surface Approximation and Geometric Partitions

Pankaj K. Agarwal and Subhash Suri

pp. 1016-1035

BibTeX  Abstract Full Text:  PDF

Randomized Data Structures for the Dynamic Closest-Pair Problem

Mordecai Golin, Rajeev Raman, Christian Schwarz, and Michiel Smid

pp. 1036-1072

BibTeX  Abstract Full Text:  PDF

Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata

Hing Leung

pp. 1073-1082

BibTeX  Abstract Full Text:  PDF

An $\Omega(\sqrt{\,\log\log n}\,)$ Lower Bound for Routing in Optical Networks

Leslie Ann Goldberg, Mark Jerrum, and Philip D. MacKenzie

pp. 1083-1098

BibTeX  Abstract Full Text:  PDF

Computing Matrix Eigenvalues and Polynomial Zeros Where the Output is Real

Dario Bini and Victor Y. Pan

pp. 1099-1115

BibTeX  Abstract Full Text:  PDF

Computational Complexity and Knowledge Complexity

Oded Goldreich, Rafail Ostrovsky, and Erez Petrank

pp. 1116-1141

BibTeX  Abstract Full Text:  PDF

The Complexity of Planar Counting Problems

Harry B. Hunt, III, Madhav V. Marathe, Venkatesh Radhakrishnan, and Richard E. Stearns

pp. 1142-1167

BibTeX  Abstract Full Text:  PDF

Guaranteeing Fair Service to Persistent Dependent Tasks

Amotz Bar-Noy, Alain Mayer, Baruch Schieber, and Madhu Sudan

pp. 1168-1189

BibTeX  Abstract Full Text:  PDF

Time--Space Lower Bounds for Directed st-Connectivity on Graph Automata Models

Greg Barnes and Jeff A. Edmonds

pp. 1190-1202

BibTeX  Abstract Full Text:  PDF

A Chernoff Bound for Random Walks on Expander Graphs

David Gillman

pp. 1203-1220

BibTeX  Abstract Full Text:  PDF